package q0148;

import java.util.List;

/**
 * 在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。
 * <p>
 * 示例 1:
 * <p>
 * 输入: 4->2->1->3
 * 输出: 1->2->3->4
 * 示例 2:
 * <p>
 * 输入: -1->5->3->4->0
 * 输出: -1->0->3->4->5
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/sort-list
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * <p>
 * <p>
 * 解题：题目要求了 nlogN 的时间复杂度
 * <p>
 * 1. 快排
 * 2. 归并
 *
 * @author fangjiaxiaobai@gmail.com
 * @version 1.0.0
 * @date 2020-05-26
 */
public class Solution {

    public ListNode sortList(ListNode head) {
        listQuickSort(head, null);
        return head;
    }

    private void listQuickSort(ListNode head, ListNode end) {
        if (end != head) {
            ListNode listNode = quickSort(head);
            listQuickSort(head, listNode);
            listQuickSort(listNode.next, end);
        }
    }

    private ListNode quickSort(ListNode head) {
        ListNode slow = head;
        ListNode fast = head.next;

        while (fast != null) {
            if (fast.val < head.val) {
                slow = slow.next;
                int temp = slow.val;
                slow.val = fast.val;
                fast.val = temp;
            }
            fast = fast.next;
            printNode(head);
        }
        int temp = slow.val;
        slow.val = head.val;
        head.val = temp;

        printNode(head);
        System.out.println();
        System.out.println();
        return slow;
    }


    public static void main(String[] args) {
        ListNode n4 = new ListNode(4);
        ListNode n2 = new ListNode(2);
        ListNode n1 = new ListNode(1);
        ListNode n3 = new ListNode(3);

        n4.next = n2;
        n2.next = n1;
        n1.next = n3;

        ListNode listNode = new Solution().sortList(n4);

        printNode(listNode);
    }

    private static void printNode(ListNode head) {
        while (null != head) {
            System.out.printf("%d\t", head.val);
            head = head.next;
        }
        System.out.println();
    }

}

